#include <iostream>

using namespace std;
struct ListNode 
{
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    // write code here
    if (pHead1 == nullptr)
    {
        return pHead2;
    }
    if (pHead2 == nullptr)
    {
        return pHead1;
    }
    ListNode* ans = new ListNode(-1);
    ListNode* ret = ans;
    while (pHead1 && pHead2)
    {
        if (pHead1->val <= pHead2->val)
        {
            ans->next = pHead1;
            pHead1 = pHead1->next;
        }
        else
        {
            ans->next = pHead2;
            pHead2 = pHead2->next;
        }
        ans = ans->next;
    }
    ans->next = pHead1 != nullptr ? pHead1 : pHead2;
    return ret->next;
}

int main()
{
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(3);
    ListNode* node3 = new ListNode(5);
    ListNode* node4 = new ListNode(2);
    ListNode* node5 = new ListNode(4);
    ListNode* node6 = new ListNode(6);
    node1->next = node2;
    node2->next = node3;
    node3->next = nullptr;
    node4->next = node5;
    node5->next = node6;
    node6->next = nullptr;

    ListNode* ans = Merge(node1, node4);
    while (ans)
    {
        cout << ans->val << " -> ";
        ans = ans->next;
    }
    cout << "nullptr";
    return 0;
}